
import java.util.*;

public class Main {
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        int top = -1;
        int i = 0;
        boolean f = true;
        int m = intervals.length;
        int[][] stack = new int[m + 1][];
        if (m == 0) {
            stack[0] = newInterval;
            return stack;
        }
        if (intervals[0][0] > newInterval[0]) {
            stack[++top] = newInterval;
            f = false;
        } else stack[++top] = intervals[i++];
        for (; i < m; i++) {
            int[] next = intervals[i];
            if (f && next[0] > newInterval[0]) {
                i--;
                next = newInterval;
                f = false;
            }
            int[] begin = stack[top];
            if (begin[1] >= next[0]) {
                int[] temp = new int[]{begin[0], next[1]};
                if (begin[1] >= next[1]) {
                    temp = new int[]{begin[0], begin[1]};
                }
                stack[top] = temp;
            } else {
                stack[++top] = next;
            }
        }
        if (f) {
            int[] temp = stack[top];
            if (temp[1] >= newInterval[0]) {
                temp[1] = Math.max(temp[1], newInterval[1]);
            } else stack[++top] = newInterval;
        }
        for (i = 0; i <= top; i++) {
            System.out.print(stack[i][0] + "," + stack[i][1] + "\t");
        }
        return Arrays.copyOfRange(stack, 0, top + 1);
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode res = new ListNode(111);
        ListNode tail = res;
        boolean f = true;
        ListNode[] nums = new ListNode[k];
        int count = 0;
        while (head != null) {
            count = 0;
            for (; count < k; count++) {
                nums[count] = head;
                head = head.next;
                if (head == null && count < k - 1) {
                    if (!f) {
                        int t = 0;
                        while (t <= count) {
                            tail.next = nums[t++];
                            tail = tail.next;

                        }
                        tail.next = null;
                    }
                    return res;
                }
            }
            ListNode temp = nums[--count];
            count--;
            for (; count >= 0; count--) {
                nums[count + 1].next = nums[count];
            }
            nums[0].next = null;
            if (f) {
                res = nums[k - 1];
                f = false;
            } else {
                tail.next = nums[k - 1];
            }
            tail = nums[0];
        }
        return res;
    }

    public static int maxArea2(int[] height) {

        int res = 0;
        int m = height.length;
        if (m < 2)
            return 0;
        int[] stack = new int[m];
        int top = -1;
        stack[++top] = 0;
        for (int i = 1; i < m; i++) {
            int n = height[i];
            for (int j = 0; j <= top; j++) {
                res = Math.max(res, (i - stack[j]) * Math.min(n, height[stack[j]]));
            }
            if (n > height[i - 1]) {
                stack[++top] = i;
            }
        }
        System.out.println(res);
        return res;
    }

    public static void setZeroes(int[][] matrix) {
        boolean flag = false;
        int m = matrix.length;
        if (m < 1)
            return;
        int n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0)
                flag = true;
            for (int j = 1; j < m - 1; j++) {

            }
        }


    }


    public static int maxArea(int[] height) {
//        height = new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7};
        int res = 0;
        int m = height.length;
        if (m < 2)
            return 0;
        int left = 0, right = m - 1;
        while (left < right) {
            res = Math.max(res, (right - left) * Math.min(height[right], height[left]));
            if (height[left] < height[right])
                left++;
            else right--;
        }

        System.out.println(res);
        return res;
    }

    public static int[][] merge(int[][] intervals) {
        int m = intervals.length;
        if (m < 2)
            return intervals;
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int[][] res = new int[m][];
        int top = -1;
        res[++top] = intervals[0];
        for (int i = 1; i < m; i++) {
            int[] next = intervals[i];
            int[] begin = res[top];
            if (begin[1] >= next[0]) {
                int[] temp = new int[]{begin[0], next[1]};
                if (begin[1] >= next[1]) {
                    temp = new int[]{begin[0], begin[1]};
                }
                res[top] = temp;
            } else {
                res[++top] = next;
            }
        }
        System.out.println(top);
        for (int i = 0; i <= top; i++) {
            System.out.print(res[i][0] + "," + res[i][1] + "\t");
        }
        return Arrays.copyOfRange(res, 0, top + 1);
    }

    public static int longestValidParentheses(String s) {
        //(()())  ()())(())()
        int q = 0;
        int res = 0;
        int now = 0;
        int left = 0;
        int right = 0;
        int i = 0;
        int m = s.length();
        for (i = 0; i < m; i++) {
            if (s.charAt(i) == '(')
                left++;
            else right++;
            now++;
            if (left < right) {
                res = Math.max(now - 1, res);
                left = 0;
                right = 0;
                now = 0;
                q++;
            }
        }

        if (i == m) {
            if (left == right) {
                res = Math.max(right * 2, res);
            } else {
                if (q == 0)
                    res = 0;
                int r = right;
                left = 0;
                right = 0;
                now = 0;
                for (i = m - 1; r > 0; i--) {
                    if (s.charAt(i) == '(')
                        left++;
                    else {
                        right++;
                        r--;
                        if (r == 0) {
                            if (i == 0)
                                return Math.max(now - 1, res);
                            return Math.max(right * 2, res);
                        }
                    }
                    now++;
                    if (left > right) {
                        res = Math.max(now - 1, res);
                        left = 0;
                        right = 0;
                        now = 0;
                    }
                }
            }
        }
        return res;
    }

    public static int longestValidParentheses2(String s) {
        int res = 0;
        int m = s.length();
        int top = -1;
        int[] stack = new int[m + 1];
        stack[++top] = -1;
        for (int i = 0; i < m; i++) {
            if (s.charAt(i) == '(') {
                stack[++top] = i;
            } else {
                top--;
                if (top == -1) {
                    stack[++top] = i;
                } else {
                    res = Math.max(i - stack[top], res);
                }
            }

        }

        return res;

    }

    public static int divide(int dividend, int divisor) {
        return dividend >> divisor;
//        System.out.println(dividend);
//        int res = 1;
//        if (dividend > 0 && divisor < 0) {
//            res = -1;
//            divisor = -divisor;
//        } else if (dividend < 0 && divisor > 0) {
//            res = -1;
//            dividend = -dividend;
//        }
//        if (dividend < divisor)
//            return 0;
//        int f=1;
//        while (divisor > 0) {
//            int i2 = divisor | 0;
//            int i1 = dividend | 0;
//            if (i1 > i2)
//                f=1;
//            else if (i1 < i2)
//                f=0;
//            dividend >>= 2;
//            divisor >>= 2;
//        }
//        int base=1;
//        int sum=0;
//        while (dividend>0){
//            sum+=(dividend|0)*base;
//            dividend >>= 2;
//            base<<=2;
//        }
//        sum+=f;
//            return res*sum;
    }

    public static String simplifyPath(String path) {
        int m = path.length();
        if (m < 2)
            return path;
        String[] stack = new String[m];
        int top = -1;
        String[] strs = path.split("/");
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].equals("") || strs[i].equals("."))
                continue;
            else if (strs[i].equals("..")) {
                if (top > -1)
                    top--;
            }//"/a/./b/../../c/"
            else stack[++top] = strs[i];
        }
        path = "";
        for (int i = 0; i <= top; i++)
            path += "/" + stack[i];
        return path == "" ? "/" : path;
    }

    public static String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2)
            return s;
        int begin = 0;
        int max_len = 1;
        char[] cs = s.toCharArray();
        boolean[][] flags = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            flags[i][i] = true;
        }
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (!(cs[i] == cs[j]))
                    flags[i][j] = false;
                else if (j - 1 < (i + 1)) {
                    if (max_len < 2) {
                        max_len = 2;
                        begin = i;
                    }
                } else {
                    flags[i][j] = flags[i + 1][j - 1];
                    if (max_len < j - i + 1) {
                        max_len = j - i + 1;
                        begin = i;
                    }
                }
            }
        }
        return String.valueOf(Arrays.copyOfRange(cs, begin, begin + max_len));
    }

    public static int searchInsert(int[] nums, int target) {
        int l = 0, right = nums.length - 1;

        while (l < right) {
            int mid = (l + right) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] == target) {
                return mid;
            } else {
                right = mid - 1;
            }
        }
        return nums[l] < target ? l + 1 : l;
    }

    public static String multiply(String num1, String num2) {
        int n1 = Integer.valueOf(num1);
        int n2 = Integer.valueOf(num2);
        String[] strings = new String[num2.length()];


        return null;
    }

    public static double myPow(double x, int n) {
        double res = 1;
        if (n == 0)
            return 1;
        boolean f = true;
        if (n < 0) {
            f = false;
            n = -n;
        }
        for (int i = 0; i < n; i++) {
            System.out.println(x);
            x *= x;
        }
        System.out.println("res:" + x);
        return f ? x : 1 / x;
    }

    public static int uniquePaths(int m, int n) {
        int[][] mat = new int[m][n];
        if (m == 1 || n == 1)
            return 1;
        for (int i = 0; i < m - 1; i++) {
            mat[i][n - 1] = 1;
        }
        for (int i = 0; i < n - 1; i++) {
            mat[m - 1][i] = 1;
        }
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                mat[i][j] = mat[i + 1][j] + mat[i][j + 1];
            }
        }

        return mat[0][0];
        //        return a(m,n,0,0);
    }

    public static int a(int m, int n, int x, int y) {
        if (x >= m || y >= n) {
            return 0;
        }
        if (x == m - 1 && y == n - 1)
            return 1;
        return a(m, n, x + 1, y) + a(m, n, x, y + 1);
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        int min = candidates[0];
        List<List<Integer>> res = new ArrayList<>();
        dfs2(res, 0, new ArrayList<>(), candidates, target, min);
        System.out.println(res);
        return res;
    }

    public static void dfs2(List<List<Integer>> res, int sum, List<Integer> list, int[] nums, int target, int min) {
        for (int i : nums) {
            if (i < min)
                continue;
            if (sum + i < target) {
                List<Integer> temp = (List<Integer>) ((ArrayList<Integer>) list).clone();
                temp.add(i);
                dfs2(res, sum + i, temp, nums, target, i);
            } else if (sum + i == target) {
                List<Integer> temp = (List<Integer>) ((ArrayList<Integer>) list).clone();
                temp.add(i);
                res.add(temp);
                return;
            } else return;
        }
    }

    public static List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        int m = digits.length();
        String str = "";
//        String str="";
        int flag=0;
        while(flag<2){
            for (int i = 0; i < m; i++) {
                int w = 3;
                char temp = digits.charAt(i);
                char c = (char) ((temp - '2') * 3 + 97);
                if (temp == '7')
                    w = 4;
                else if (temp == '8')
                    c = 't';
                else {
                    c = 'w';
                    w = 4;
                }
                if (flag==1) {
                    for (int j = 0; j < w; j++) {
//                        res.get(i*)

                    }
                } else {
                    for (int j = 0; j < w; j++) {
                        res.add(new String());
                    }
                }
            }
            flag++;
        }


        return res;
    }
    public static int largestRectangleArea(int[] heights) {
        int res=0;
        int m=heights.length;
        int []left=new int[m];
        int []right=new int[m];
        Stack<Integer>stack=new Stack<>();
        for(int i=0;i<heights.length;i++){
            while(!stack.empty()&&heights[stack.peek()]>heights[i]){
                int idx_left = stack.pop();
                res=Math.max(res,(i-idx_left)*heights[idx_left]);
            }
            stack.add(i);
        }
        while (!stack.empty()){
            int idx_left = stack.pop();
            res=Math.max(res,(heights.length-idx_left)*heights[idx_left]);
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(largestRectangleArea(new int[]{4,2,4}));
        Solution solution = new Solution();
//        System.out.println(solution.isMatch("abcddd","abc*d"));
//        solution.nextPermutation(new int[]{1, 2, 3, 4});
        List<Map<Integer, Integer>> l = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
//        solution.getPermutation(l,map,0,4);
//        Math.pow()
//        System.out.println(l);
//        solution.threeSum2(new int[]{0,0, 0,0});
        System.out.println(simplifyPath("/../"));
//        System.out.println(divide(10, 3));
//        insert(new int[][]{{1, 3}}, new int[]{2, 5});
//        maxArea(new int[]{1, 2, 1});
//        setZeroes(new int[][]{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}});
//        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 4));
//        System.out.println(myPow(2,10));
//        System.out.println(uniquePaths(3,7));
//            combinationSum(new int[]{1},2);
//        System.out.println((char) (('7' - '2') * 3 + 97));

    }


}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}